/*
题目链接：https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days/description/
1011. 在D天内送达包裹的能力-中等
完成日期：2024/9/24
二分搜索
*/
class Solution {
public:
    int count_(vector<int> &weights){
        long long ans=0;
        for(int x:weights){
            ans+=x;
        }
        return ans;
    }
    int shipWithinDays(vector<int>& weights, int days) {
        int l=*max_element(weights.begin(),weights.end());
        int r=count_(weights);
        while(l<r){
            int mid=(l+r)/2;
            int d=1;
            int w=0;
            for(int k:weights){
                if(w+k>mid){
                    d++;
                    w=0;
                }
                w+=k;
            }
            if(d<=days){
                r=mid;
            }else{
                l=mid+1;
            }
        }
        return l;
    }
};